package _08_DFS_BFS;

import java.util.ArrayList;
import java.util.List;

/**
 * https://leetcode-cn.com/problems/generate-parentheses/
 * @Author: haogege
 * @Date: 2021/8/31
 */
public class _22_括号生成 {

    private int len;

    public List<String> generateParenthesis(int n) {
        List<String> list = new ArrayList<>();
        // 1, 2可以穷举出来
        if (n == 1) {
            list.add("()");
            return list;
        } else if (n == 2) {
            list.add("()()");
            list.add("(())");
            return list;
        }
        len = n << 1;
        char[] result = new char[n];
        dfs(0, result, n, n, list);
        return list;
    }

    private void dfs(int i, char[] result, int remainLeft, int remainRight, List<String> list) {
        if (i == len) {
            list.add(new String(result));
            return;
        }
        // 穷举所有可能
        if (remainLeft >= 0) {
            result[i] = '(';
            dfs(i + 1, result, remainLeft - 1, remainRight, list);
        }

        if (remainRight >= 0 && remainLeft != remainRight) {
            result[i] = ')';
            dfs(i + 1, result, remainLeft, remainRight - 1, list);
        }
    }
}
